/*
 * Written by Farzon Lotfi
 * HW  5
 * MyHashTable.java
 * Collaboration statement: I worked on this on my own
 * */

import java.util.List;
import java.util.LinkedList;
import java.util.ListIterator;

/**
 * @author Farzon Lotfi 
 * @version 1.0
 * class that acts as MyHashTable has three field values
 * the bucket array, the array size (could have uses .length but this way was
 * had less lines of code)
 */
public class MyHashTable<K, V> implements ITable<K, V> {

	private LinkedList<MyHashEntry<K, V>>[] bucketArray;
	private int arraySize;
	private int elementCount;

	
	/**
	 * constructor that takes in an arraySize
	 * then creates an array of linked lists with that size
	 * @param int arraySize - an integer of the size array you want
	 */
	public MyHashTable(int arraySize) {
		this.arraySize = arraySize;
		this.bucketArray = (LinkedList<MyHashEntry<K,V>>[]) new LinkedList[arraySize];
	}

	/**
	 * takes in a key gets a hash code then compresses it using a simple mod
	 * @param K key
	 * @return integer value so you know where in the bucket array to store it
	 */
	public int hash(K key) {
		int total = 0;

		if (key == null) 
			return -1;

		for(int i=0; i < key.toString().length(); i++) {
			total += (key.toString().charAt(i));
		}

		//see which count to use?
		return total%arraySize;
	}


	/**
	 * Clears the hash table so that it contains no keys or values. The
	 * capacity of the hash table should not be changed
	 */
	public void clear() {
		this.elementCount = 0;
		this.bucketArray = (LinkedList<MyHashEntry<K,V>>[]) new LinkedList[arraySize];
	}

	/**
	 * Determines whether the key is currently in the hash table.
	 * @param key the key to check for
	 * @return true if the key is in the hash table, false otherwise
	 */
	public boolean containsKey(K key) {
		if(bucketArray[hash(key)] != null) {
			ListIterator  iterator = bucketArray[hash(key)].listIterator();
			while(iterator.hasNext()){
				K currentKey = ((MyHashEntry<K, V>) 
						iterator.next()).getKey();
				if(currentKey.equals(key))
					return true;
			}
		}
		return false;
	}
	
	/**
	 * Determines whether the key is currently in the hash table. Deletes the node if it is.
	 * @param key the key to check for
	 * @return true if the key is in the hash table and is successfully deleted, false otherwise
	 */
	public boolean delNode(K key,V value) 
	{
		LinkedList<MyHashEntry<K, V>> curr_list = bucketArray[hash(key)];
		if(curr_list != null)
		{
			ListIterator  iterator = curr_list.listIterator();
			while(iterator.hasNext())
			{
				MyHashEntry<K, V> current = ((MyHashEntry<K, V>) 
						iterator.next());
				K currentKey = current.getKey();
				V currValue  = current.getValue();
				if(currentKey.equals(key))
				{
					if(currValue.equals(value))
					{
						curr_list.removeFirstOccurrence(current);
						elementCount--;
						return true;
					}
				}
			}
		}
		return false;
	}


	/**
	 * Determines whether the value is currently in the hash table
	 * @param value the value to check for
	 * @return true if the value is in the hash table, false otherwise
	 */
	public boolean containsValue(V value) {
		//brute force attempt, check with craig for better way
		for(int i = 0;i<bucketArray.length;i++){
			if (bucketArray[i] != null) {
				ListIterator  iterator = bucketArray[i].listIterator();
				while(iterator.hasNext()){
					V currentVal = ((MyHashEntry<K, V>) 
							iterator.next()).getValue();
					/*System.out.println("current value: "+ currentVal +
								" check value: "+value);*/
					if(currentVal.equals(value))
						return true;
				}
			}
		}
		return false;
	}

	/**
	 * Get all values from the hash table that have the key. Returns
	 * null if the key passed in is null or if the key does not have any values.
	 * @param key the key to get all the values for
	 * @return a List of values with the specified key in the hash table or null
	 */
	public List<V> getAll(K key) {
		if(key == null)
			return null;

		if(bucketArray[hash(key)] != null) {
			List<V> listOfValues = new LinkedList<V>();
			ListIterator  iterator = bucketArray[hash(key)].listIterator();
			while(iterator.hasNext()){
				MyHashEntry<K, V> current = ((MyHashEntry<K, V>) 
						iterator.next());
				if(current.getKey().equals(key))
					listOfValues.add(current.getValue());
			}
			return listOfValues;
		}
		return null;
	}

	/**
	 * Determines whether the hash table is empty.
	 * @return false if there is at least one value in the hash table,
	 * true otherwise.
	 */
	public boolean isEmpty() {
		if (elementCount == 0)
			return true;
		return false;
	}

	/**
	 * Inserts the value into the hashTable using the key.
	 * 
	 * The key should be hashed by taking all of the chars that make up its
	 * string representation and adding them together. For instance:
	 * 'cat' = 99 + 97 + 116
	 * Be sure to handle the case in which the hash > capacity of hash table.
	 * 
	 * If the load factor > .75 with the addition of this new value then 
	 * call reHash before performing the new insert. See the reHash javadoc
	 * for more information.
	 * 
	 * If the key is null (no String representation) then do not perform the
	 * insert and return false.
	 * 
	 * @param key the key to use to insert the value
	 * @param value the value to insert into the hash table
	 * @return true if successfully added, false otherwise
	 */
	public boolean put(K key, V value) {
		int hash_val = hash(key);
		if(hash(key)==-1)
			return false;
		double percentage = (double)elementCount/arraySize;
		
		if(percentage>=.75){
			reHash();
		}
		
		if(hash(key) > arraySize){

			if(bucketArray[hash(key)-arraySize]==null)
				bucketArray[hash(key)-arraySize] = new LinkedList<MyHashEntry<K, V>>();
			elementCount++;
			bucketArray[hash(key)-arraySize].addFirst(new MyHashEntry<K,V>(key,value));
		}
		else {
			if(bucketArray[hash(key)]==null)
				bucketArray[hash(key)] = new LinkedList<MyHashEntry<K, V>>();
			elementCount++;
			bucketArray[hash(key)].addFirst(new MyHashEntry<K,V>(key,value));
		}
		return true;
	}

	/**
	 * Should only be called when the load factor of the hash table > 0.75.
	 * This function doubles the size of the hash table and then rehashes
	 * every entry into the new hash table.
	 */
	public void reHash() {
		this.arraySize = 2*arraySize;
		LinkedList<MyHashEntry<K,V>>[] bucketTemp = 
			(LinkedList<MyHashEntry<K,V>>[]) new LinkedList[arraySize];
		
		for(int i = 0;i<bucketArray.length;i++){
			if (bucketArray[i] != null) {
				ListIterator  iterator = bucketArray[i].listIterator();
				while(iterator.hasNext()){
					MyHashEntry<K, V> current = ((MyHashEntry<K, V>) 
							iterator.next());
					if (null == bucketTemp[hash(current.getKey())])
						bucketTemp[hash(current.getKey())] = new LinkedList<MyHashEntry<K,V>>();
					
					bucketTemp[hash(current.getKey())].add(current);
					
				}
				
			}
		}
		bucketArray = bucketTemp;

	}
	/**
	 * Returns the number of values (NOT KEYS) currently held in the
	 * hash table.
	 * @return the number of values in the hash table
	 */
	public int size() {
		return elementCount;
	}
	
	public int arr_size() {
		return arraySize;
	}

	/**
	 * This must create a string representation of the hash table and
	 * return it. It should print the index of the hash table first and
	 * then list the key, value pairs held at that index. For instance,
	 * a possible representation of a hash table of size 5 could be:
	 * 
	 * "0: (red, George) (red, Grace)
	 *  1:
	 *  2: (Magenta, Cindy)
	 *  3: (Blue, Fred) (Blue, Tom) (Blue Ian)
	 *  4: (Green Rob)"
	 *  
	 *  The entries being printed are in the following format: (key, value)
	 *  If a value in a hash entry is null then just print: (key null)
	 *  
	 *  Index 1 did not have any entries so it was left blank.
	 *  
	 * @return the string representation of the hash table
	 */
	public String toString(){
		String returnString = "";
		for(int i = 0;i<bucketArray.length;i++){
			if (bucketArray[i] != null){
				List<V> listOfValues = new LinkedList<V>();
				ListIterator  iterator = bucketArray[i].listIterator();
				returnString += i+":";
				while(iterator.hasNext()){
					MyHashEntry<K, V> current = ((MyHashEntry<K, V>) 
							iterator.next());
					returnString += " ("+current.getKey().toString()+", "+
					current.getValue().toString()+") ";  
				}
				returnString +="\n";
			}
			else
				returnString += i+": \n";
		}
		return returnString;
	}

	public LinkedList<MyHashEntry<K, V>>[] getBucketArray() {
		return bucketArray;
	}

	public void setBucketArray(LinkedList<MyHashEntry<K, V>>[] bucketArray) {
		this.bucketArray = bucketArray;
	}

	/**
	 *main method used here to test my code
	 */
	public static void main(String[] args) {
		MyHashTable<Double, String> test = new MyHashTable<Double, String>(7);

		//isEmpty() test works
		System.out.println(" expected: true, actual: "+test.isEmpty());

		//put works
		test.put(.5, "hello");
		System.out.println(test.toString());
		test.put(.75, "good bye");
		System.out.println(test.toString());
		test.put(5., "go");
		System.out.println(test.toString());
		test.put(4.5, "my");
		System.out.println(test.toString());
		test.put(3.5, "friday");
		System.out.println(test.toString());
		test.put(2.5, "saturday");
		System.out.println(test.toString());

		//containsValue works
		System.out.println("\ncontainsKey() test");
		System.out.println("expected true, actual: "+test.containsKey(.5));
		System.out.println("expected true, actual: "+test.containsKey(.75));
		System.out.println("expected true, actual: "+test.containsKey(4.5));
		System.out.println("expected true, actual: "+test.containsKey(5.));
		System.out.println("expected true, actual: "+test.containsKey(3.5));
		System.out.println("expected true, actual: "+test.containsKey(2.5));
		System.out.println("expected false, actual: "+test.containsKey(1.5));

		//rehash works
		System.out.println();
		test.put(1.5, "nope");
		System.out.println(test.toString());

		//containsValue works
		System.out.println("\ncontainsKey() test 2");
		System.out.println("expected true, actual: "+test.containsKey(.5));
		System.out.println("expected true, actual: "+test.containsKey(.75));
		System.out.println("expected true, actual: "+test.containsKey(4.5));
		System.out.println("expected true, actual: "+test.containsKey(5.));
		System.out.println("expected true, actual: "+test.containsKey(3.5));
		System.out.println("expected true, actual: "+test.containsKey(2.5));
		System.out.println("expected true, actual: "+test.containsKey(1.5));
		System.out.println("expected false, actual: "+test.containsKey(2.358));

		//containsValue works
		System.out.println("\ncontainsValue() test");
		System.out.println("expected true, actual: "+test.containsValue("hello"));
		System.out.println("expected true, actual: "+test.containsValue("good bye"));
		System.out.println("expected true, actual: "+test.containsValue("go"));
		System.out.println("expected true, actual: "+test.containsValue("my"));
		System.out.println("expected true, actual: "+test.containsValue("friday"));
		System.out.println("expected true, actual: "+test.containsValue("saturday"));
		System.out.println("expected true, actual: "+test.containsValue("nope"));
		System.out.println("expected false, actual: "+test.containsValue("does not exist"));

		//size() test works
		System.out.println("\nsize() test");
		System.out.println("expected Size: 7, actual size: "+test.size());

		//isEmpty() test works
		System.out.println("\niEmpty() test");
		System.out.println("expected: false, actual: "+test.isEmpty());


		//getAll() test works
		System.out.println("\ngetAll() test");
		test.put(1.5, "number 2");
		System.out.println(test.getAll(1.5).toString());

		//clear() test works
		System.out.println("\nclear() test");
		System.out.println("Before:\n"+test.toString());
		test.clear();
		System.out.println("After:\n"+test.toString());

		//getAll() test works
		System.out.println("\ngetAll() test");
		test.put(1.5, "number 2");
		System.out.println(test.getAll(1.5));
		test.put(1.5, "number 3");
		System.out.println(test.getAll(1.5));
		test.put(1.5, "number 4");
		System.out.println(test.getAll(1.5));
		test.put(2.5, "numero 4");
		System.out.println(test.getAll(2.5));
		test.put(2.5, "numero 2");
		System.out.println(test.getAll(2.5));
		
		System.out.println(test.getAll(3.5));
		

	}
}